As known in the art, a non-negative quadratic program (NNQP)
                                                                                          min                  x                                ⁢                                                      1                    2                                    ⁢                                      x                    T                                    ⁢                  Qx                                            -                                                x                  T                                ⁢                h                                                                        s              .              t              .                                                                          x                ≥                0                            ,                                                          (        1        )            with vectorsx,h εn,and a symmetric positive semi-definite matrixQεn×n,where T is a transpose operator is ubiquitous in image processing applications, where x is a vector of non-negative quantities, such as light intensities, to be estimated under a squared error norm.
For example, Eq. (1) subsumes a non-negative least squares (NNLS) problem encountered in deblurring and super-resolution applications,
                                                                        min                x                            ⁢                                                                                      Ax                    -                    b                                                                    2                2                                                                        s              .              t              .                                                                          x                ≥                0                            ,                                                          (        2        )            withQ=AT A and h=ATb.where A is a blurring or downsampling matrix, and b is a vector of pixel values. Eq. (1) is also the dual of a broader class of convex quadratic programs of the form
                                                                                                                                                            min                        y                                            ⁢                                                                        1                          2                                                ⁢                                                  y                          T                                                ⁢                        Hy                                                              -                                                                  y                        T                                            ⁢                      f                                                                                                            s                    .                    t                    .                                                                                                                          Ay                ≥                b                            ,                                                          (        3        )            h are derived from vectors f, b are matrices A, and H via a dual transform.
Such quadratic programs are used in image labeling and image segmentation applications, and image operations that involve solving Poisson equation, e.g., matting. Solutions of Eq. (1) yield solutions of Eq. (3).
Eqs. (1-3) are well know in the prior art. State-of-the-art interior-point, active-set, and primal-dual algorithms offer linear-to-quadratic rates of convergence, but each iteration requires solution of a linear equation at least as large as Qy=z, which can take O(n3) time for a vector y of n values. This is impractical for image processing, where the number n of pixels in a single image can be 107 or larger, Obviously this is an extremely complex operation and cannot simply be performed.
Multiplicative update methods are suitable for very large problems. They allow rough estimates of the solution vector to be improved without solving linear equations. Some well-known examples are the Richardson-Lucy deblurring algorithm, the image-space reconstruction algorithm, and Lee-Seung non-negative matrix factorization algorithm. These will turn out to be special cases of the invention presented here.
However, those applications rely on some combination of strictly nonnegative coefficients, positive definiteness, or favorable initialization for convergence, if convergence is provable at all.